package zach.parser;

import java.util.ArrayList;
import java.util.EnumSet;
import java.util.HashMap;
import java.util.LinkedList;

import util.Function;
import util.StringReader;
import util.Util;
import util.ZachError;
import zach.env.Env;
import zach.env.Keyword;
import zach.env.LexType;
import zach.env.MarkPattern;
import zach.env.WordType;

public final class Lex {
	static boolean isLowerCase( int ch ) {
		return ch >= 'a' && ch <= 'z';
	}

	static boolean isAlpha( int ch ) {
		return ( ch >= 'a' && ch <= 'z' ) || ( ch >= 'A' && ch <= 'Z' );
	}

	static boolean isDigit( int ch ) {
		return ch >= '0' && ch <= '9';
	}

	static boolean isTokenChar( int ch ) {
		return isAlpha( ch ) || isDigit( ch ) || ch == '_';
	}

	static boolean isBlank( int ch ) {
		return ch == ' ' || ch == '\t' || ch == '\n';
	}

	final static Function<Word, StringReader> readToken = TokenReader( Env.keywords ); // 读标记函数

	/**
	 * 制作一个Token阅读器,可以分析出一般id和关键字
	 * 
	 * @param keywords
	 *            支持的关键字数组
	 * @return 阅读Token的函数
	 */
	static Function<Word, StringReader> TokenReader( Keyword[] keywords ) {
		// Token树的节点类型
		class Node {
			public Node[] next = new Node[26];
			public WordType type = null; // 使用了可空类型
		}

		final Node root = new Node(); // 根节点

		// 遍历关键字,构造Token树
		for ( Keyword keyword : keywords ) {
			Node curNode = root; // 当前节点

			// 遍历字符串,构造路径
			String str = keyword.str;
			for ( int i = 0, len = str.length(); i != len; ++i ) {
				char c = str.charAt( i );
				// 检查关键字字符是否是小写字母
				assert isLowerCase( c ) : "Keyword must be lowercase";

				// 创建路径,并更新当前节点位置
				int index = c - 'a'; // 在路径中的索引
				curNode.next[index] = new Node();
				curNode = curNode.next[index];
			}

			// 路径构造完毕
			// 判断是否有重复的关键字
			assert curNode.type == null : "Reduplicate keyword";

			// 更新该路径的词类型
			curNode.type = keyword.wordType;
		}

		return new Function<Word, StringReader>() {
			@Override
			public Word call( StringReader stringReader ) throws ZachError {
				boolean isKeyword = true; // 当前是否是关键词
				Node curNode = root; // 当前节点
				LinkedList<Integer> value = new LinkedList<Integer>(); // 值

				// 遍历Token树
				while ( true ) {
					int ch = stringReader.cur(); // 取出当前字符

					// 如果不是Token字符,跳出遍历
					if ( !isTokenChar( ch ) ) {
						// 根据当前节点的类型选择返回的是关键字还是id
						return isKeyword && curNode.type != null ? new Word( curNode.type, null ) : new Word( WordType.ID, value.toArray( new Integer[] {} ) );
					}
					else {
						// 如果当前仍处于keyWord状态,继续进行路径
						if ( isKeyword ) {
							if ( isLowerCase( ch ) && curNode.next[ch - 'a'] != null ) {
								curNode = curNode.next[ch - 'a'];
							}
							else {
								isKeyword = false;
							}
						}

						// 更新值,并读新的字符
						value.add( ch );
						stringReader.eat();
					}
				}
			}
		};
	}

	// 判断一个字符是否是ascii字符,并且是否属于一个ascii表
	static boolean containAscii( boolean[] asciiMaps, int ch ) {
		return ch < 128 && ch >= 0 && asciiMaps[ch] == true;
	}

	static final boolean[] ValidMarkPatternChars = Util.AsciiMap( Env.MarkString.concat( "a\n" ) ); // 合法的符号模式字符表
	static final boolean[] MarkChars = Util.AsciiMap( Env.MarkString ); // 符号字符表

	/**
	 * 制作符号阅读器
	 * 
	 * @param markPatterns
	 *            支持的符号模式
	 * @return 阅读符号的函数
	 */
	static Function<Word, StringReader> MarkReader( MarkPattern[] markPatterns ) {
		// 状态图的节点类型
		class State {
			public HashMap<Integer, State> next = new HashMap<Integer, State>();
			public WordType type = null; // 可空类型
		}

		final State root = new State();

		// 遍历模式,构造状态图
		for ( MarkPattern pattern : markPatterns ) {
			String str = pattern.string; // 模式字符串
			State curState = root; // 当前状态
			State aState = null; // a状态

			// 模式字符串中,a必须自中间,否则异常
			assert str.charAt( 0 ) != 'a' && str.charAt( str.length() - 1 ) != 'a' : "Error mark-pattern";

			// 遍历模式字符串,构造状态路径
			for ( int i = 0, len = str.length(); i != len; ++i ) {
				int ch = str.charAt( i );
				// 确保模式字符串都是有效字符
				assert containAscii( ValidMarkPatternChars, ch ) : "Error mark-pattern";

				if ( ch == 'a' ) {
					// 只能有一个通配符
					assert aState != null : "Error mark-pattern";

					// 处理a,将aState设置为当前state
					aState = curState;
				}
				else {
					// 处理其它字符,如果没有路径,铺设路径
					if ( curState.next.get( ch ) == null ) {
						curState.next.put( ch, new State() );
					}

					// 如果有a,构成循环
					if ( aState != null ) {
						curState.next.put( ( int ) 'a', aState );
					}

					curState = curState.next.get( ch );
				}
			}

			// 不允许有重复的模式
			assert curState.type == null : "Reduplicate mark-pattern";

			// 设置该条路径的type
			curState.type = pattern.wordType;
		}

		return new Function<Word, StringReader>() {
			@Override
			public Word call( StringReader stringReader ) throws ZachError {
				State curState = root; // 当前状态

				// 爬状态表
				while ( true ) {
					int ch = stringReader.cur(); // 读字符

					// 如果有路,往下走
					if ( curState.next.get( ch ) != null ) {
						curState = curState.next.get( ch );
					}
					// 如果没有路,看看有没有全匹配,若有,进入全匹配
					else if ( curState.next.get( ( int ) 'a' ) != null ) {
						curState = curState.next.get( ( int ) 'a' );
					}
					// 否则跳出循环
					else {
						break;
					}

					stringReader.eat(); // 吃字符
				}

				// 没有匹配上任何符号,抛出错误
				if ( curState.type == null ) throw new ZachError( ParseError.UnrecognisedMark );

				return new Word( curState.type, null );
			}

		};
	}

	// 读一个(字符串)字符,并吃掉它
	static int eatChar( StringReader stringReader ) throws ZachError {
		int ch = stringReader.cur(); // 读出字符
		stringReader.eat(); // 吃掉该字符

		// 如果读到的是反斜杠,处理转义
		if ( ch == '\\' ) {
			ch = stringReader.cur(); // 读待转义字符
			if ( !Env.escapeMap.containsKey( ch ) ) throw new ZachError( ParseError.InvalidChar ); // 如果不支持该转义,抛出异常
			ch = Env.escapeMap.get( ch ); // 解转义
			stringReader.eat(); // 吃掉转义字符
		}

		// 读到了EOF,报错
		if ( ch == -1 ) throw new ZachError( ParseError.UnexpectedEOF );

		return ch;
	}

	// 填充类,使用模板模式模仿函数作为参数的函数
	static abstract class FillWith {
		abstract protected boolean fillMode( int ch );

		// 从一个StringReader中向一个链表中填充指定模式的值,若填充失败抛出错误
		public void fill( LinkedList<Integer> value, StringReader stringReader, ParseError parseError ) throws ZachError {
			if ( !fillMode( stringReader.cur() ) ) throw new ZachError( parseError );

			// 填充value
			while ( true ) {
				int ch = stringReader.cur();
				if ( !fillMode( ch ) ) {
					return;
				}
				value.add( ch );
				stringReader.eat();
			}
		}
	}

	static final class FillWithDigit extends FillWith {
		@Override
		protected boolean fillMode( int ch ) {
			return isDigit( ch );
		}
	}

	static final class FillWidthAlphaDigit extends FillWith {
		@Override
		protected boolean fillMode( int ch ) {
			return isAlpha( ch ) || isDigit( ch );
		}
	}

	// 字符表作为分支,相较于if结构,有更好的速度,更适合词法分析
	static final class CharBranchs implements Function<Word, StringReader> {
		ArrayList<Function<Word, StringReader>> branchs = new ArrayList<Function<Word, StringReader>>(); // 分支数组

		public CharBranchs() {
			// 加128个空,否则set方法不能用
			for ( int i = 0; i != 128; ++i ) {
				branchs.add( null );
			}
		}

		// 添加一个分支
		public void addBranch( String chars, Function<Word, StringReader> stmt ) {
			// 遍历字符串,未字符串中的每个字符建立一个分支
			for ( int i = 0, len = chars.length(); i != len; ++i ) {
				branchs.set( ( int ) chars.charAt( i ), stmt );
			}
		}

		@Override
		public Word call( StringReader stringReader ) throws ZachError {
			// 根据当前读出的字符进行分支
			int ch = stringReader.cur();

			// 是ascii字符,查表跳转
			if ( ch >= 0 && ch < 128 ) {
				Function<Word, StringReader> branch = branchs.get( ch ); // 取出分支
				if ( branch != null ) {
					return branch.call( stringReader );
				}
			}

			// 处理EOF
			if ( ch == -1 ) {
				return new Word( WordType.EOF, null );
			}

			// 什么都不是,抛出错误
			throw new ZachError( ParseError.UnexpectedWord );
		}
	}

	/**
	 * 根据参数,制作一个读词函数
	 * 
	 * @param lexTypes
	 *            要解析的词的类型,包括Token和Value
	 * @param markPatterns
	 *            要解析的符号
	 * @return 可以解析指定词类型的读词函数
	 */
	public static Function<Word, StringReader> WordReader( EnumSet<LexType> lexTypes, MarkPattern[] markPatterns ) {
		CharBranchs charBranchs = new CharBranchs();

		// 空白符分支
		charBranchs.addBranch( "\t\n ", new Function<Word, StringReader>() {
			@Override
			public Word call( StringReader stringReader ) throws ZachError {
				stringReader.eat();

				// 读到不是空白符为止
				while ( isBlank( stringReader.cur() ) ) {
					stringReader.eat();
				}

				return new Word( WordType.BLANK, null );
			}
		} );

		// Token分支
		if ( lexTypes.contains( LexType.Token ) ) {
			charBranchs.addBranch( "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_", readToken );
		}

		// Value分支
		if ( lexTypes.contains( LexType.Value ) ) {
			// 字符分支
			charBranchs.addBranch( "'", new Function<Word, StringReader>() {
				@Override
				public Word call( StringReader stringReader ) throws ZachError {
					stringReader.eat(); // 吃掉前单引号
					int ch = eatChar( stringReader ); // 读字符
					if ( stringReader.cur() != '\'' ) throw new ZachError( ParseError.InvalidChar ); // 字符后必须跟着单引号
					stringReader.eat(); // 吃掉后单引号
					return new Word( WordType.CHAR, new Integer[] { ch } );
				}
			} );

			// 字符串分支
			charBranchs.addBranch( "\"", new Function<Word, StringReader>() {
				@Override
				public Word call( StringReader stringReader ) throws ZachError {
					LinkedList<Integer> value = new LinkedList<Integer>(); // 值
					stringReader.eat(); // 吃掉前双引号

					// 如果没读到后双引号,吃字符
					while ( stringReader.cur() != '"' ) {
						value.add( eatChar( stringReader ) );
					}
					stringReader.eat(); // 吃掉后双引号

					return new Word( WordType.STRING, value.toArray( new Integer[] {} ) );
				}
			} );

			// 数字分支
			charBranchs.addBranch( "0123456789", new Function<Word, StringReader>() {
				@Override
				public Word call( StringReader stringReader ) throws ZachError {
					WordType wordType;
					LinkedList<Integer> value = new LinkedList<Integer>(); // 值

					// 如果开头以0开始,表示特殊数字
					if ( stringReader.cur() == '0' ) {

						stringReader.eat(); // 吃掉0

						// 根据下一个字符决定不同的进制
						switch ( stringReader.cur() ) {
							case 'x':
							case 'X':
								wordType = WordType.HEX;
								break;
							case 'o':
							case 'O':
								wordType = WordType.OCTAL;
								break;
							case 'b':
							case 'B':
								wordType = WordType.BINARY;
								break;
							case 'd':
							case 'D':
								wordType = WordType.DECIMAL;
								break;
							default:
								// 否则直接抛异常
								throw new ZachError( ParseError.InvalidNumber );
						}
						stringReader.eat(); // 吃掉进制标志

						// 填充字符
						new FillWidthAlphaDigit().fill( value, stringReader, ParseError.InvalidNumber );
					}
					else {
						// 处理一般数字,包括整数,小数和指数
						wordType = WordType.DECIMAL;
						new FillWithDigit().fill( value, stringReader, ParseError.InvalidNumber ); // 填充数字

						// 处理小数
						if ( stringReader.cur() == '.' ) {
							value.add( ( int ) '.' ); // 添加小数点到值中
							stringReader.eat(); // 吃掉小数点
							wordType = WordType.DOUBLE; // 现在类型是Double
							new FillWithDigit().fill( value, stringReader, ParseError.InvalidNumber ); // 填充数字
						}

						// 处理指数
						int ch = stringReader.cur();
						if ( ch == 'e' || ch == 'E' ) {
							value.add( ch ); // 添加e到值中
							stringReader.eat(); // 吃掉e
							wordType = WordType.DOUBLE; // 现在类型是Double
							new FillWithDigit().fill( value, stringReader, ParseError.InvalidNumber ); // 填充数字
						}
					}

					return new Word( wordType, value.toArray( new Integer[] {} ) );
				}
			} );

		}

		// Mark分支
		// 计算生成MarkReader所需要的MarkPatterns,即合并ZachAnnotation和参数中的markPattern
		MarkPattern[] allMarkPatterns = new MarkPattern[markPatterns.length + Env.ZachAnnotation.length];
		int i = 0;
		for ( MarkPattern pattern : markPatterns ) {
			allMarkPatterns[i++] = pattern;
		}
		for ( MarkPattern pattern : Env.ZachAnnotation ) {
			allMarkPatterns[i++] = pattern;
		}
		charBranchs.addBranch( Env.MarkString, MarkReader( allMarkPatterns ) );

		return charBranchs;
	}
}
